package 树与图.字典树;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;


/**
 * 103. 二叉树的锯齿形层序遍历
 *
 *  思路： 还是层序遍历，所以继续考虑BFS，但是因为是锯齿状，需要对层数考虑奇偶性，奇数从左到右，偶数从右到左
 *
 *  解题思路
 * 层序遍历框架：使用队列进行标准的层序遍历，逐层处理节点。
 *
 * 方向控制：使用一个布尔变量 leftToRight 控制当前层的方向。初始方向为从左到右（根节点层）。
 *
 * 节点值插入方式：
 * 当方向为从左到右时，将节点值按顺序添加到列表尾部。
 * 当方向为从右到左时，将节点值插入到列表头部（利用链表的头插法实现，时间复杂度为O(1)）。
 *
 * 切换方向：每处理完一层后，切换方向，以便下一层按相反顺序处理。
 */
public class L_103 {

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null){
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        // 使用一个布尔变量控制方向
        boolean leftToRight = true;
        while (!queue.isEmpty()){
            int size = queue.size();
            LinkedList<Integer> list = new LinkedList<>();
            for (int i = 0; i < size; i++) {
                TreeNode poll = queue.poll();
                // 从左到右，从前向后
                if(leftToRight){
                    list.addLast(poll.val);
                }else {
                    // 从右到左，从后向前
                    list.addFirst(poll.val);
                }
                if(poll.left!=null){
                    queue.offer(poll.left);
                }
                if(poll.right!= null){
                    queue.offer(poll.right);
                }
            }
            res.add(list);
            // 切换方向
            leftToRight = !leftToRight;
        }
        return res;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
